package com.lijing.SingleLinkedList;

import java.util.Stack;

//定义一个单链表来管理影英雄
public class SingleLinkedList {
    //初始化一个头节点，头节点一般不要动
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    //添加节点到单向链表,不考虑序号
    public void addHeroNode(HeroNode hero){
        //需要一个临时中间节点辅助
        HeroNode temp = head;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = hero;
    }

    //添加节点到单向链表，考虑顺序
    public void addByOrder(HeroNode hero){
        HeroNode temp = head;
        boolean flag = false;
        while(true){
            //如果为空直接添加
            if (temp.next == null){
                break;
            }
            //如果非空，找到要添加的位置
            if(temp.next.no > hero.no){//找到位置，添加到temp的后面
                break;
            }else if(temp.next.no == hero.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断flag值
        if(flag){//编号已存在
            System.out.printf("准备插入的英雄的编号%d已经存在,不能加入！",hero.no);
        }else{
            hero.next = temp.next;
            temp.next = hero;
        }
    }

    //显示链表
    public void showList(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("list is empty!");
            return;
        }
        HeroNode temp = head.next;
        while(temp != null){
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //修改节点，no不变，修改其他值，遍历链表，
    public void update(HeroNode newHeroNode){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;//用于标志有没有可修改的数据，即有没有该no的节点
        while (true){
            if (temp == null){//链表已经遍历完成,直接退出
                break;
            }
            if(temp.no == newHeroNode.no){//找到需要修改更新的节点
                flag = true;//表示找到
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else {
            System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
        }
    }

    //删除节点，根据no来删除，直接将要删除的节点的上一节点的next指向删除节点的下一节点就ok
    public void del(int no){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空！");
        }
        //链表非空，遍历链表找到要删除的节点，注意还要判断有没有这个节点存在
        HeroNode temp = head;
        boolean flag = false;//false不存在，true表示存在
        while (true){
            if(temp.next == null){//遍历结束，还没找到，直接退出
                break;
            }
            if (temp.next.no == no){//找到了要删除的节点
                flag = true;
                break;
            }
            temp = temp.next;//temp后移
        }
        if (flag){//存在要删除的节点
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的no为%d的节点不存在\n",no);
        }
    }

    //求单链表中的有效节点的个数,如果带头节点的链表，不统计头节点
    //思路分析，遇到一个有效节点就+1
    public static int getLength(HeroNode head){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空！");
        }
        int length = 0;
        HeroNode temp = head.next;
        while (temp != null){
           length++;
           temp = temp.next;
        }
        return length;
    }

    //查找单链表倒数第k个节点
    //思路分析：求出链表的有效个数size，倒数第k个其实就是正数第size-k个节点。如1234567，倒数第2个，节点从1开始只需移动5次就得到6
    public static HeroNode getLastIndex(HeroNode head, int index){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空！");
        }
        //先遍历链表，查看要查找的index符不符合要求
        int length = SingleLinkedList.getLength(head);
        if (index <= 0 || index >length){//index校验
            System.out.printf("找不到倒数第%d的节点",index);
            return null;
        }
        HeroNode cur = head.next;//直接指向节点
        for (int i = 0; i < length-index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //单链表的反转
    //思路：新建一个链表，用来进行头插入，遍历原来链表，没遇到一个节点就取出，加入到新链表的头部后面一个节点，最后将原链表的head.next指向新链表的head.next
    public static void reverseList(HeroNode head){
        //如果链表为空或只有一个节点，则无需更改，直接返回
        if(head.next == null || head.next.next ==null){
            return;
        }
        //否则遍历原链表
        HeroNode tempHead = new HeroNode(0,"","");//新链表的头节点
        HeroNode cur = head.next;//直接指向当前遍历的节点
        HeroNode tempNext = cur.next;//用于保存当前遍历到的节点的下一个节点
        //遍历完毕
        while (cur != null) {
            tempNext = cur.next;
            cur.next = tempHead.next;
            tempHead.next = cur;
            cur = tempNext;
        }
        //遍历完毕后,将原链表的头接到新链表上
        head.next = tempHead.next;

    }

    //逆序打印单链表
    //利用栈数据结构，遍历原链表，利用栈先进后出特点实现逆序打印
    public static void reversePrint(HeroNode head){
        //判断链表是否为空或只有一个节点
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        Stack<HeroNode> heroNodes = new Stack<HeroNode>();
        HeroNode temp = head.next;
        while (temp != null){
            heroNodes.add(temp);
            temp =  temp.next;
        }
        while (heroNodes.size() > 0){
            System.out.println(heroNodes.pop());
        }
    }
}
